8.7 二分查找

二分查找是一种高效的查找算法，它通过将有序数组逐步对半分割的方式快速定位目标元素。

二分查找的效率远高于线性查找，适用于大规模数据集，但前提是数组必须是有序的。

简单来说就是将数组分成两半，之后将中间元素与查找目标值进行比较，这样就可以决定下一步从前半部分还是后半部分查找。

通过二分就可以将线性的查找步骤减少了一半，同时如果对二分后再二分，那么效率就会更进一步提高。

本节代码存放目录为 lesson23

概念与原理

二分查找的原理如下：

• 通过比较目标值与数组中间元素的大小来决定在左半部分还是右半部分继续查找。

• 每次将待查找的范围缩小一半，直到找到目标值或查找范围为空。

二分查找适用于有序数组，其时间复杂度为 O(log n)，在较大数据集上具有很高的查找效率。

二分查找的步骤示例如下：

给定如下有序数组，目标是查找元素 4：

[2, 3, 4, 5, 8]

通过二分查找的步骤如下：

第一轮：

- 查找范围：[2, 3, 4, 5, 8]，中间元素为 4。

- 比较目标值 4 与中间元素 4，相等，查找成功，返回索引 2。

在第一轮查找时就已经找到了目标值 4，因此查找结束，返回索引 2。

二分查找的时间复杂度

二分查找的时间复杂度为 O(log n)，因为每次查找都将问题规模缩小一半：

• 最坏情况：O(log n)，即目标值位于数组的两端或不在数组中。

• 最好情况：O(1)，即目标值位于数组的中间。

• 平均情况：O(log n)，即目标值随机分布在数组中。

由于二分查找的高效性，它特别适合用于数据量大且有序的数组。

Go语言的实现

我们可以在 Go 语言中轻松实现二分查找算法：

// binarySearch 实现二分查找
func binarySearch(arr []int, target int) int {
    low := 0               // 查找范围的起始点
    high := len(arr) - 1    // 查找范围的结束点

    // 当查找范围不为空时
    for low <= high {
        mid := low + (high-low)/2 // 计算中间元素索引

        // 如果目标值与中间元素相等，查找成功
        if arr[mid] == target {
            return mid
        }

        // 如果目标值小于中间元素，缩小查找范围到左半部分
        if target < arr[mid] {
            high = mid - 1
        } else {
            // 如果目标值大于中间元素，缩小查找范围到右半部分
            low = mid + 1
        }
    }

    // 如果找不到，返回 -1
    return -1
}

func main() {
    arr := []int{2, 3, 4, 5, 8}
    target := 4

    // 执行二分查找
    result := binarySearch(arr, target)

    if result != -1 {
        fmt.Printf("元素 %d 找到，索引为: %d\n", target, result)
    } else {
        fmt.Println("元素未找到")
    }
}

执行结果如下所示：

元素 4 找到，索引为: 2

在上面的代码中，binarySearch 函数通过比较目标值与中间元素的大小，逐步缩小查找范围，直到找到目标值或范围为空。

递归实现的二分查找

二分查找还可以通过递归的方式实现，如下所示：

// binarySearchRecursive 递归实现二分查找
func binarySearchRecursive(arr []int, low int, high int, target int) int {
    // 基线条件，查找范围为空
    if low > high {
        return -1
    }

    // 计算中间元素索引
    mid := low + (high-low)/2

    // 查找成功
    if arr[mid] == target {
        return mid
    }

    // 目标值小于中间元素，递归查找左半部分
    if target < arr[mid] {
        return binarySearchRecursive(arr, low, mid-1, target)
    }

    // 目标值大于中间元素，递归查找右半部分
    return binarySearchRecursive(arr, mid+1, high, target)
}

func main() {
    arr := []int{2, 3, 4, 5, 8}
    target := 4

    // 执行递归二分查找
    result := binarySearchRecursive(arr, 0, len(arr)-1, target)

    if result != -1 {
        fmt.Printf("元素 %d 找到，索引为: %d\n", target, result)
    } else {
        fmt.Println("元素未找到")
    }
}

执行结果与非递归实现相同，递归实现代码更简洁一些，也比较容易看懂。

小结

本节我们讲解了二分查找的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：二分查找的时间复杂度为 O(log n)，适合用于大规模有序数据集。

• 局限性：二分查找只能用于有序数组，如果数组无序，必须先进行排序。

• 应用场景：二分查找适用于查找频繁的数据集，例如搜索引擎、数据库查询等场景。